package com.graph;

import java.util.*;

public class Solution1615 {
    public int maximalNetworkRank(int n, int[][] roads) {
        int[] inDeg = new int[n];
        Set<Integer>[] g = new HashSet[n];
        for (int i = 0; i < n; i++)
            g[i] = new HashSet<>();
        for (int[] road : roads) {
            inDeg[road[0]]++;
            inDeg[road[1]]++;
            g[road[0]].add(road[1]);
            g[road[1]].add(road[0]);
        }

        int first = 0, second = -1;
        for (int i = 0; i < n; i++)
            if (first < inDeg[i]) {
                second = first;
                first = inDeg[i];
            } else if (second < inDeg[i])
                second = inDeg[i];

        List<Integer> firstList = new ArrayList<>(), secondList = new ArrayList<>();
        for (int i = 0; i < n; i++)
            if (first == inDeg[i])
                firstList.add(i);
            else if (second == inDeg[i])
                secondList.add(i);

        int size = firstList.size();
        if (size == 1) {
            int firstIdx = firstList.get(0);
            for (int secondIdx : secondList)
                if (!g[firstIdx].contains(secondIdx))
                    return first + second;
            return first + second - 1;
        } else {
            if (size * (size - 1) / 2 > roads.length)
                return first * 2;
            for (int i = 0; i < size - 1; i++)
                for (int j = i + 1; j < size; j++)
                    if (!g[firstList.get(i)].contains(firstList.get(j)))
                        return first * 2;
            return first * 2 - 1;
        }
    }
}
